{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 大文件排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 场景：在 4 GiB 内存的单机上对 100 GB 文件排序。\n",
    "- 难点：数据远超内存，只能分块读写——典型的 **外部排序 (external sorting)** 问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "两阶段解决方案概览\n",
    "\n",
    "1. **分块排序阶段**\n",
    "   - 将大文件分成若干 1 GiB 的块（示例假设）。\n",
    "   - 每个块：读入内存 → 内存排序 → 写回磁盘生成中间有序“run”。\n",
    "   - 可选优化：\n",
    "     - 单线程：读/排/写串行，CPU 和磁盘交替空闲。\n",
    "     - 单盘双线程：IO 线程串行读写 + 排序线程池，实现 IO 与排序重叠，内存占用 ≈ 2×chunk。\n",
    "     - 双盘多线程：分别为读盘、写盘配 IO 线程，进一步压缩时间，内存≈3×chunk。\n",
    "     - 最后几个块留在内存，不再落盘，直接进入归并，可省下一轮 IO。\n",
    "2. **多路归并阶段**\n",
    "   - 对所有有序 run 做一次性 **N 路归并**。\n",
    "   - 使用 `std::make_heap / std::pop_heap / std::push_heap` 构建最小堆，每个堆元素包含当前记录及其来源文件。\n",
    "   - 循环取出堆顶最小值写入输出，并从同一 run 读入下一条数据重新入堆；run 耗尽即从堆中移除。\n",
    "   - 相比多轮二路归并，减少了大量磁盘读写。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "扩展思路与相关问题\n",
    "\n",
    "- 查找两个 ~100 GB 文件间少量重复行：\n",
    "  1. **哈希分桶**：按 hash 划分成许多 ≤1 GiB 小文件，再在内存中逐一求交集。\n",
    "  2. **双多路归并**：分别对 a、b 分块排序并用两个堆同步归并，边归并边求交集（代码较复杂，因为需要维护两个堆的状态）。\n",
    "- 如果语言有 coroutine / `yield`，可把多路归并包装成迭代器，直接交给 `std::set_intersection` 等算法。\n",
    "- 思考如何在外部排序中减少额外磁盘占用（例如复用空间、流式处理）。\n",
    "- 类似实战：统计多个巨型 query 日志中每个 query 的出现次数（可在外排序框架下实现）。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
